package com.adee.algorithm.structure.s01_stack;

import java.util.Stack;

public class Test003_Expression {
    public static void main(String[] args) {
        // test1();
        test2();
    }

    /*
    * 使用栈计算表达式
    * 例如，计算 [7*2*2-5+1-5+3-4*2]，有两种思路，
    * 第一种： 使用一个栈，栈中即可以放数字也可以放符号
    *         1. 先将表达式字符串构造成一个二叉树；
    *         2. 后序方式入栈，即先把两个子节点入栈，再把当前节点入栈。
    * 第二种： 使用两个栈，一个放数字，另一个放符号
    *         1. 通过一个索引index，从左到右顺序遍历表达式字符串；
    *         2. 如果我们发现是一个数字，就直接入数栈；
    *         3. 如果发现扫描到的是一个符号，那么分如下情况；
    *         4. 如果发现当前的符号栈为空，就直接入栈；
    *         5. 如果符号栈有操作符，就进行比较，如果当前操作符优先级小于或等于栈中的操作符，
    *            就需要从数栈中pop出两个数，从符号栈中pop出一个符号，计算后结果压入数栈，此时还没结束，
    *            继续while循环检查当前符号栈顶的符号优先级和当前符号的优先级，处理逻辑同上，一直到当前
    *            符号优先级大于符号栈顶符号优先级才结束，即把当前符号压入符号栈，如果当前操作符优先级大
    *            于栈中操作符，则直接把当前操作符入栈；
    *         6. 当表达式扫描完毕，就顺序地从数栈和符号栈中pop出相应的数和符号，并运行；
    *         7. 最后在数栈中只有一个数，就是表达式结果。
    *
    * */
    public static void test1() {
        Stack<Node> s = new Stack<>();
        s.push(new Node("7"));
        s.push(new Node("2"));
        s.push(new Node("*"));
        s.push(new Node("2"));
        s.push(new Node("*"));
        s.push(new Node("5"));
        s.push(new Node("-"));
        s.push(new Node("1"));
        s.push(new Node("+"));
        s.push(new Node("5"));
        s.push(new Node("-"));
        s.push(new Node("3"));
        s.push(new Node("+"));
        s.push(new Node("4"));
        s.push(new Node("2"));
        s.push(new Node("*"));
        s.push(new Node("-"));

        int res = (int)getValue(s);
        System.out.println("7*2*2-5+1-5+3-4*2 = " + res);
    }
    // 一个栈方式实现表达式运算
    public static Object getValue(Stack<Node> st) {
        if(!st.isEmpty()) {
            Node e = st.pop();
            String val = (String)e.value;
            switch (val) {
                case("+"):
                    return (int)getValue(st) + (int)getValue(st);
                case("-"):
                    int v1 = (int)getValue(st);
                    int v2 = (int)getValue(st);
                    return  v2 - v1;
                case("*"):
                    return (int)getValue(st) * (int)getValue(st);
                case("/"):
                    return (int)getValue(st) / (int)getValue(st);
                default:
                    return Integer.parseInt(val);
            }
        }
        return null;
    }

    // 两个栈方式实现测试
    public static void test2() {
//        String str = "7*2*12-5+1-15+13-4*12";
//        int r = getValue2(str);
//        System.out.println(str + " = " + r);

        // String str2 = "11*2*8-5+1-15*1890+20-4*12/8*173+256*12-79";
        String str2 = "11*2*8-5+1-15*1890+20";
        int r2 = getValue2(str2);
        System.out.println(str2 + " = " + r2);

        String str3 = "11*2*8-5+1-15*1890+20-4*12/8*173";
        int r3 = getValue2(str3);
        System.out.println(str3 + " = " + r3);

        String str4 = "11*2*8-5+1-15*1890+20-4*12/8*173+256*12-79";
        int r4 = getValue2(str4);
        System.out.println(str4 + " = " + r4);
    }
    // 两个栈方式实现
    public static int getValue2(String str) {
        Stack<Integer> nums = new Stack<>();
        Stack<Character> flags = new Stack<>();
        StringBuilder sb = new StringBuilder();
        int len = str.length();
        for (int i = 0; i < len; i++) {
            char c = str.charAt(i);
            if(c >= '0' && c <= '9') {
                sb.append(c);
                if(i == len-1) {
                    nums.push(Integer.parseInt(sb.toString()));
                }
            } else if(c == '+' || c == '-' || c == '*' || c == '/') {
                nums.push(Integer.parseInt(sb.toString()));
                sb = new StringBuilder();
                if(!flags.isEmpty() && le(c, flags.peek())) { // 当前运算符优先级小于等于栈中运算符，先计算值，再入栈
                    // 插入新的运算符之前，保证符号栈上前面挨着的运算符优先级都小于当前符号，否则一直弹出符号栈顶符号并计算
                    while(!flags.isEmpty() && le(c, flags.peek())) {
                        int v1 = nums.pop();
                        int v2 = nums.pop();
                        nums.push(calc(v2, v1, flags.pop()));
                    }
                }
                flags.push(c);
            }
        }
        // 全部入栈后，进行顺序出栈计算
        while(!flags.isEmpty()) {
            int v1 = nums.pop();
            int v2 = nums.pop();
            nums.push(calc(v2, v1, flags.pop()));
        }
        if(nums.isEmpty()) {
            throw new IllegalStateException("nums栈中操作数数量错误");
        } else {
            return nums.pop();
        }
    }

    // 符号a的运算优先级小于或等于符号b，返回true，否则返回false
    public static boolean le(char a, char b) {
        String s = "+-*/";
        if(s.indexOf(a) < 0) {
            throw new IllegalArgumentException("le 运算符号不在 +-*/ 范围内：" + a);
        }
        if(s.indexOf(b) < 0) {
            throw new IllegalArgumentException("le 运算符号不在 +-*/ 范围内：" + a);
        }
        if((a == '*' || a == '/') && (b == '+' || b == '-')) { // a > b
            return false;
        } else { // a <= b
            return true;
        }
    }

    // 计算
    public static int calc(int a, int b, char flag) {
        switch (flag) {
            case ('+'):
                return a + b;
            case ('-'):
                return a - b;
            case ('*'):
                return a * b;
            case ('/'):
                return a / b;
            default:
                throw new IllegalArgumentException("calc 运算符号不在 +-*/ 范围内：" + flag);
        }
    }

    public static void test3() {

    }

    static class Node<V> {
        V value;
        public Node(V v) {
            value = v;
        }
    }
}
